package zuochengyun.chapter8;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;
import list.LinkedListCreate;
import list.LinkedListUtil;
import list.ListNode;
import util.PrintArray;

import java.util.*;

/**
 * 数组左侧的小于等于某个数，右侧大于某个数
 * Created by shuowu on 2018/1/10.
 */
public class LeftLessRightMore {

    public static void main(String[] args){
        LeftLessRightMore object = new LeftLessRightMore();
//        Random random = new Random();
//        int[] array = {18, 23, 9, 0, 14, 15, -13, -24, 98, 27, 9};
//        int[] array = new int[30];
//        for (int i = 0; i < array.length; i++) {
//            array[i] = random.nextInt(1000) - 500;
//        }
//        object.heapSort(array);
//        for (int i = 0; i < array.length; i++) {
//            System.out.print(" " + array[i]);
//        }
        //test linkedlist partition
//        ListNode head = LinkedListCreate.createList(array);
//        head = object.partition_4(head, 124);
//        LinkedListCreate.printList(head);
//        System.out.println("the index is " + index);

        //test kmp
//        System.out.println(object.find("bas", "s"));
//        System.out.println(object.kmp("bassadascds", "as"));

//        int[] pre = {1, 3, 5, -1, 6, 9, 2, 8, 10, 4, 15};
//        int[] in = {5, -1, 3, 9, 2, 6, 1, 10, 4, 8, 15};
//        TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
//        object.postOrder(root);
//        object.printByLevel(root);
//        System.out.println(object.lengthOfLongestSubstring_2("pwwkew"));

        //test bigInteger multiply
//        int[] a = {9, 8, 1, 8, 7};
//        int[] b ={1, 4};
//        int[] res = object.bigIntegerMul(a, b);
//        PrintArray.printArray(res);

//        int[] test = {9, 6, 13, 7, 3, 4, -8, 5, 9, 10};
//        int[] res = object.getFirstMore(test);
//        PrintArray.printArray(res);


//        int[] pre = {15, 5, 1, -5, 3, 10, 8, 20};
//        int[] in = {-5, 1, 3, 5, 8, 10, 15, 20};
//        TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
//        TreeNode res = object.getNearestNode(root, 18);
//        System.out.println("res: " + res.val);

        //object.getRemovedKDigit(978457892323L, 4);
//        int[] array = {2, 3, 1, 5, 9, 8};
//        System.out.println(object.getMaxRes(array));
//        System.out.println(object.getGCD(23, 30));
    }

    public int getRes(int[] array, int key){
        if(array == null || array.length <= 0){
            return -1;
        }
        //就是一个partition
        int start = 0;
        int end = array.length - 1;
        //这个和partition有一点不同的是start < end就行
        while(start < end){
            while(start < end && array[start] <= key){
                start++;
            }
            while(start < end && array[end] > key){
                end--;
            }
            if(start < end){
                swap(array, start, end);
            }
        }
        return start;
    }

    public boolean swap(int[] array, int i, int j){
        System.out.println(i + " swap " + j);
        if(array == null || array.length < j || array.length < i || i < 0 || j < 0){
            System.err.println("the index is invalid or array is null");
            return false;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        return true;
    }

    public void heapSort(int[] array){
        if (array == null || array.length <= 0){
            return;
        }
        //初始建堆
        for (int i = array.length / 2; i >= 0; i--) {
            heapAdjust(array, i, array.length);
            //printArray(array);
        }
        //交换然后调整堆
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            heapAdjust(array, 0, i);
        }
    }

    public void printArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(" " + array[i]);
        }
        System.out.println();
    }
    //调整堆，以i结点为跟的左子树和右子树已经为堆，大根堆
    //i的值是经过更新过的值，可能小于左右两个堆的值
    public void heapAdjust(int[] array, int index, int length){
        if(index > length / 2){
            return;
        }
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int max = index;
        System.out.println(index + "length :" + length);
        if(left < length && array[left] > array[max]){
            max = left;
        }
        if(right < length && array[right] > array[max]){
            max = right;
        }
        if(max != index) {
            swap(array, index, max);

            heapAdjust(array, max, length);
        }
    }


    //链表的partition，wrong version
    public int partition(ListNode head, int key){
        if(head == null || head.next == null){
            return 0;
        }
        ListNode oneNode = null;
        ListNode twoNode = null;
        ListNode twoHead = null;
        ListNode node = head;
        int res = 0;
        //最开始的想法是反转链表然后类似partition，后来发现反转其实也需要O(n)
        while (node != null ) {
            if(node.val < key){
                if(oneNode != null) {
                    oneNode.next = new ListNode(node.val);
                    oneNode = oneNode.next;
                } else {
                    oneNode = new ListNode(node.val);
                    //这样子不行，因为head改变了指向，但是并没有改变实参中的head
                    head = oneNode;
                }
                res++;
            } else {
                if(twoNode != null) {
                    twoNode.next = new ListNode(node.val);
                    twoNode = twoNode.next;
                } else {
                    twoNode = new ListNode(node.val);
                    twoHead = twoNode;
                }
            }
            node = node.next;
        }
        if(oneNode != null) {
            oneNode.next = twoHead;
        }
        return res;
    }

    //链表的partition，wrong version
    public int partition_2(ListNode head, int key){
        if(head == null || head.next == null){
            return 0;
        }
        ListNode oneNode = null;
        ListNode twoNode = null;
        ListNode twoHead = null;
        ListNode node = head;
        //copyHead 指向拷贝的新的链表
        ListNode copyHead = null;
        ListNode temp = head;
        while (temp != null) {
            if(copyHead == null) {
                copyHead = new ListNode(temp.val);
                node = copyHead;
            } else {
                node.next = new ListNode(temp.val);
                node = node.next;
            }
            temp = temp.next;
        }
        int res = 0;
        node = copyHead;
        //最开始的想法是反转链表然后类似partition，后来发现反转其实也需要O(n)
        //18, 23, 9, 0, 14, 15, -13, -24, 98, 27, 9    key 25
        //当我们第二个链表赋值的时候twoNode = node;
        //node.next并没有清除，所以可能会导致node
        while (node != null) {
            if(node.val < key){
                if(oneNode != null) {
                    oneNode.next = node;
                    oneNode = oneNode.next;
                } else {
                    //改变head 的值
                    head.val = node.val;
                    oneNode = head;
                }
                res++;
            } else {
                if(twoNode != null) {
                    twoNode.next = node;
                    twoNode = twoNode.next;
                } else {
                    twoNode = node;
                    twoHead = twoNode;
                }
            }
            node = node.next;
        }
        //very important, 预防第二段的尾还连着原始的node
        if(twoNode != null) {
            twoNode.next = null;
        }
        LinkedListCreate.printList(head);
        System.out.println("_____");
        LinkedListCreate.printList(twoHead);
        if(oneNode != null) {
            oneNode.next = twoHead;
        }
        return res;
    }

    //这个重新复制了链表，不是一个好的实现
    public ListNode partition_3(ListNode head, int x) {
        if(head == null){
            return null;
        }
        ListNode less = new ListNode(0);
        ListNode more = new ListNode(0);
        ListNode lessHead = less;
        ListNode moreHead = more;
        ListNode temp = head;
        while(temp != null){
            if (temp.val < x) {
                less.next = new ListNode(temp.val);
                less = less.next;
            } else {
                more.next = new ListNode(temp.val);
                more = more.next;
            }
            temp = temp.next;
        }
        less.next = moreHead.next;
        return lessHead.next;
    }

    public ListNode partition_4(ListNode head, int x) {
        if(head == null){
            return null;
        }
        ListNode less = new ListNode(0);
        ListNode more = new ListNode(0);
//        less.next = head;
//        more.next = head;
        ListNode lessHead = less;
        ListNode cur = head;
        ListNode pre = more;
        while (cur != null) {
            if (cur.val < x) {
                less.next = cur;
                pre.next = cur.next;
                cur = cur.next;
                less = less.next;
                less.next = null;
            } else {
                pre.next = cur;
                pre = cur;
                cur = cur.next;
            }
        }
        less.next = more.next;
        //如果直接用pre
        while(pre.next != null){
            if(pre.next.val < x){
                less.next = pre.next;
                less = less.next;
                pre.next = pre.next.next;
                //强制置空，以免链表指向其它节点
                less.next = null;
            } else {
                pre = pre.next;
            }
        }
        //more.lext 是在 pre.next = pre.next.next;中更新的
        pre.next = more.next;
        return lessHead.next;
    }

    public ListNode revertList(ListNode head){
        //反转链表
        ListNode revert = head;
        ListNode pre = null;
        ListNode next = null;

        while (revert != null){
            next = revert.next;
            revert.next = pre;
            pre = revert;
            revert = next;
        }
        return pre;
    }


    //KMP
    public boolean find(String string, String find) {
        if (string == null || string.length() <= 0 || find == null || find.length() <= 0) {
            return false;
        }
        char[] str = string.toCharArray();
        char[] mode = find.toCharArray();
        int[] next = new int[mode.length];
        getNext(next, find);
        int index = 0;
        for (int i = 0; i < str.length; i++) {
            if(str[i] == mode[index]){
                index++;
                if(index == mode.length) {
                    //found the mode
                    return true;
                }
            } else {
                while (index > 0 && str[i] != mode[index]) {
                    index = next[index - 1];
                }
                if(str[i] == mode[index]){
                    index++;
                }
            }

        }
        return false;
    }

    public int kmp(String string, String find) {
        if (string == null || string.length() <= 0 || find == null || find.length() <= 0) {
            return 0;
        }
        char[] str = string.toCharArray();
        char[] mode = find.toCharArray();
        int[] next = new int[mode.length];
        getNext(next, find);
        int index = 0;
        int res = 0;
        for (int i = 0; i < str.length; i++) {
            if(str[i] == mode[index]){
                index++;
                if(index == mode.length) {
                    //found the mode
                    res++;
                    if(index > 0){
                        index = next[index - 1];
                    } else {
                        index = 0;
                    }
                }
            } else {
                while (index > 0 && str[i] != mode[index]) {
                    index = next[index - 1];
                }
                if(str[i] == mode[index]){
                    index++;
                }
            }

        }
        return res;
    }

    //获取next数组
    public void getNext(int[] next, String find){
        if (next == null || next.length < find.length()) {
            return;
        }
        next[0] = 0;
        int k = 0;
        char[] string = find.toCharArray();
        for (int i = 1; i < next.length; i++) {
            if (string[i] == string[k]) {
                next[i] = next[i - 1] + 1;
                k++;
            } else {
                while (k > 0 && string[i] != string[k]) {
                    //如果不匹配之后，移动k就行
                    //之前一直很奇怪为什么不 + 1
                    //后来发现已经匹配的长度是next[i - 1],那么对应的下标是next[i - 1] - 1
                    //接下来匹配下一个时，加一，所以是next[i - 1]
                    k = next[i - 1];
                }
                if (string[i] == string[k]) {
                    k++;
                }
                next[i] = k;
            }
        }
    }


    // TODO 1. 层次遍历
    // 2.
    //不递归求中序或者前序遍历
    public void preOrder(TreeNode root){
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                System.out.print(node.val + " ");
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()) {
                node = stack.pop().right;
            }
        }
        System.out.println();
    }

    // 无递归的中序遍历
    public void inOrder(TreeNode root){
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode temp;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()) {
                temp = stack.pop();
                System.out.println(temp.val + " ");
                node = temp.right;
            }
        }
        System.out.println();
    }

    //采用第二种思路，先加右、左节点，然后加父节点
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp;
        TreeNode pre = null;
        stack.push(root);
        //注意要先将右节点和左节点加入之后，才能加父节点
        while (!stack.isEmpty()) {
            temp = stack.peek();
            //两种情况下可以访问父节点，1是左右节点都是null
            // 2就是左右节点都访问过之后
//            System.out.println("cur pre: " + (pre == null ? null : pre.val));
            // 知道这个pre != null的含义了
            // 因为初始时pre = null, 如果遍历到一个节点没有左子树或者右子树
            // 那么(pre == temp.left || pre == temp.right)就是真, 所以导致出现错误
            if( (temp.left == null && temp.right == null) || (pre != null && (pre == temp.left || pre == temp.right))){
                temp = stack.pop();
                System.out.println(temp.val);
                pre = temp;
                continue;
            }
            if(temp.right != null){
                stack.push(temp.right);
            }
            if(temp.left != null){
                stack.push(temp.left);
            }
        }
        System.out.println();
    }

    public void printByLevel(TreeNode root){
        if(root == null){
            return;
        }
        int nextToBePrint = 1;
        int nextLevelNodes = 0;
        LinkedList<TreeNode> list = new LinkedList<>();
        TreeNode curNode = root;
        list.add(curNode);
        while (!list.isEmpty()) {
            curNode = list.removeFirst();
            nextToBePrint--;
            System.out.print(curNode.val + " ");
            if(curNode.left != null) {
                list.add(curNode.left);
                nextLevelNodes++;
            }
            if(curNode.right != null) {
                list.add(curNode.right);
                nextLevelNodes++;
            }
            if(nextToBePrint == 0){
                nextToBePrint = nextLevelNodes;
                nextLevelNodes = 0;
                System.out.println();
            }
        }
    }

    //最长无重复子串，总是想要这么写，但是是不对的
    // 比如abba，最后一个a去找第一个a，但是中间有两个b
    public int lengthOfLongestSubstring(String s) {
        int[] index = new int[256];
        Arrays.fill(index, -1);
        if(s == null || s.length() <= 0){
            return 0;
        }
        char[] array = s.toCharArray();
        int res = 0;
        int cur = 0;
        for (int i = 0; i < array.length; i++){
            if (index[array[i]] == -1){
                cur++;
                if( cur > res) {
                    res = cur;
                }
            } else {
                cur = i - index[array[i]];
                res = Math.max(res, cur);
            }
            index[array[i]] = i;
        }
        return res;
    }

    public int lengthOfLongestSubstring_2(String s) {
        int[] index = new int[256];
        Arrays.fill(index, -1);
        if(s == null || s.length() <= 0){
            return 0;
        }
        char[] array = s.toCharArray();
        int res = 0;
        int cur = 0;
        //pre表示必须以str[i - 1]结尾时最长无重复字符的起始位置的前一个位置
        int pre = -1;
        for (int i = 0; i < array.length; i++){
            //因为最长也就是上一次出现的位置a
            //但是pre位置可能在a的前面或者后面，所以需要取最大的
            //而且后面的最长扩展肯定不可能在pre之前，因为后面只会多字符
            // 比如 pre.....i 是最长的
            // pre......i i + 1那就多了一个字符，i都扩展不到pre之前，所以i+ 1更不会扩展到pre之前
            pre = Math.max(pre, index[array[i]]);
            cur = i - pre;
            res = Math.max(res, cur);
            index[array[i]] = i;
        }
        return res;
    }


    //大数据相加, 存储方式是从低位到高位
    public int[] bigIntegerAdd(int[] a, int[] b){
        if(a == null || a.length <= 0) {
            return b;
        }
        if(b == null || b.length <= 0) {
            return a;
        }
        System.out.println(a.length + " b length: " + b.length);
        //保证a的长度长
        if (a.length < b.length) {
            return bigIntegerAdd(b, a);
        }
        int cur = 0;
        int carry = 0;
        int temp = 0;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if( i < b.length) {
                temp = carry + a[i] + b[i];
            } else {
                temp = carry + a[i];
            }
            cur = temp % 10;
            carry = temp / 10;
            result.add(cur);
        }
        if (carry != 0) {
            result.add(carry);
        }
        int[] res = new int[result.size()];
        int index = 0;
        for (int digit : result) {
            res[index++] = digit;
        }
        return res;
    }


    //存储方式是从低位到高位
    public int[] bigIntegerMul(int[] a, int[] b){
        if(a == null || a.length <= 0) {
            return b;
        }
        if(b == null || b.length <= 0) {
            return a;
        }
        //保证a的长度长
        if (a.length < b.length) {
            return bigIntegerMul(b, a);
        }
        //最多m + n位
        int[] result = new int[a.length + b.length];
        int cur = 0;
        int temp = 0;
        int curDigit = 0;
        for (int i = 0; i < b.length; i++) {
            int addCarry = 0;
            int mulCarry = 0;
            for (int j = 0; j < a.length; j++) {
                temp = a[j] * b[i] + mulCarry;
                cur = temp % 10;
                mulCarry = temp / 10;
                temp = result[i + j] + cur + addCarry;
                curDigit = temp % 10;
                addCarry = temp / 10;
                result[i + j] = curDigit;
            }
            if (addCarry != 0 || mulCarry != 0) {
                temp = mulCarry + addCarry;
                result[i + a.length] = temp % 10;
                result[i + a.length + 1] = temp / 10;
            }
            System.out.println(Arrays.toString(result));
        }
        return result;
    }


    //查找倒数第k个节点
    public ListNode getKthNode(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        //第一个指针先走 k - 1步
        ListNode quick = head;
        ListNode slow = head;
        for (int i = 0; i < k - 1; i ++) {
            if(quick != null) {
                quick = quick.next;
            } else {
                System.err.println("the list don't contain k nodes");
                return null;
            }
        }
        while(quick.next != null) {
            quick = quick.next;
            slow = slow.next;
        }
        return slow;
    }

    //获取两个节点的最近公共祖先
    //这个比剑指Offer上的简单多了
    public TreeNode getCommonAncestor(TreeNode head, TreeNode node1, TreeNode node2) {
        if (head == null || node1 == head || node2 == head) {
            return head;
        }
        //在左、右子树中是否含有node1或者node2, 如果不含有返回null
        TreeNode left = getCommonAncestor(head.left, node1, node2);
        TreeNode right = getCommonAncestor(head.right, node1, node2);
        //左、右子树分别含有其中一个节点
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }

    //单调栈的应用
    //返回数组中每一个数右边第一个比他大的
    public int[] getFirstMore(int[] array){
        if(array == null || array.length <= 0) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[array.length];
        for (int i = 0; i < array.length; i++){
//            if(stack.isEmpty() || array[stack.peek()] > array[i]) {
//                stack.push(i);
//            } else {
                while (!stack.isEmpty() && array[stack.peek()] < array[i]) {
                    res[stack.pop()] = array[i];
                }
                stack.push(i);
//            }
        }
        while (!stack.isEmpty()) {
            res[stack.pop()] = -1;
        }
        return res;
    }

    //找到二叉搜索树中最接近val的节点
    public TreeNode getNearestNode(TreeNode root, int val){
        if(root == null || root.val == val) {
            return root;
        }
        TreeNode left = getNearestNode(root.left, val);
        TreeNode right = getNearestNode(root.right, val);
        int leftDiff = Integer.MAX_VALUE;
        int rightDiff = Integer.MAX_VALUE;
            if(left != null) {
            leftDiff = Math.abs(left.val - val);
        }
        if (right != null) {
            rightDiff = Math.abs(right.val - val);
        }
        int cur = Math.abs(root.val - val);
        if (leftDiff < rightDiff) {
            if (leftDiff < cur) {
                return left;
            } else {
                return root;
            }
        } else {
            if (rightDiff < cur) {
                return right;
            } else {
                return root;
            }
        }
    }

    //remove k digit 得到最大的数
    public long getRemovedKDigit(long num, int k) {
        //assert k > num.length
        //贪心算法
        // num 是否为负
        int[] digit = new int[64];
        int index = 0;
        while (num != 0) {
            digit[index++] = (int) (num % 10);
            num /= 10;
        }
        int removeCount= 0;
        int[] res = new int[64];
        int resIndex = 0;
        outer:
        for (int i = index - 1; i > 0; i--){
            if (removeCount >= k) {
                System.arraycopy(digit, 0, res, resIndex, i + 1);
                break;
            }
            //如果高位的数字小于下一位的数字，删除高位的就行
            while (digit[i] < digit[i - 1]){
                i--;
                removeCount++;
                if (removeCount >= k) {
                    System.arraycopy(digit, 0, res, resIndex, i + 1);
                    break outer;
                }
            }
            res[resIndex++] = digit[i];
        }
        long result = 0;
        int cur= 1;
        PrintArray.printArray(digit);
        System.out.println("the res is ");
        PrintArray.printArray(res);

        for (int i = resIndex - 1; i >= 0; --i) {
            result += res[i] * cur;
            cur *= 10;
        }
        return result;
    }

    //子数组中的最小值乘以子数组的和最大
    public int getMaxRes(int[] array) {
        if (array == null || array.length <= 0) {
            return 0;
        }

        int res = 0;
        int[] sum = new int[array.length];
        //左边第一个大于i的数字的下标
        int[] left = new int[array.length];
        //右边第一个大于i的数字的下标
        int[] right = new int[array.length];
        sum[0] = array[0];
        Stack<Integer> stack = new Stack<>();
        for (int i = array.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && array[stack.peek()] > array[i]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            left[stack.pop()] = -1;
        }
        for (int i = 0; i < array.length; i++) {
            if (i == 0) {
                sum[i] = array[0];
            } else {
                sum[i] = sum[i - 1] + array[i];
            }
            while (!stack.isEmpty() && array[stack.peek()] > array[i]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            right[stack.pop()] = -1;
        }
        System.out.println("left____");
        PrintArray.printArray(left);
        System.out.println("right_____");
        PrintArray.printArray(right);
        System.out.println("array____");
        PrintArray.printArray(sum);
        for (int i = 0; i < array.length; i++) {
            int leftIndex = left[i] == -1 ? 0 : (left[i] + 1 > i ? i : left[i] + 1);
            int rightIndex = right[i] == -1 ? array.length - 1 : (right[i] - 1 < i ? i : right[i] - 1);
            int curSum = sum[rightIndex] - sum[leftIndex] + array[leftIndex];
            System.out.println("left:" + leftIndex + "right " + rightIndex + " curSum: " + curSum);
            if (curSum * array[i] > res){
                res = curSum * array[i];
                System.out.println(res);
            }
        }
        return res;
    }


    // again kmp practise
    public int[] getNextArray(char[] chars) {
        if(chars == null || chars.length <= 0) {
            return new int[]{};
        }
        int[] next = new int[chars.length];
        next[0] = 0;
        int index = 0;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == chars[index]) {
                index++;
                next[i] = next[i - 1] + 1;
            } else {
                while (index > 0 && chars[i] != chars[index]) {
                    index = next[index - 1];
                }
                if (chars[i] == chars[index]){
                    index++;
                }
                next[i] = index;
            }
        }
        return next;
    }

    // 获取最大公约数
    public int getGCD(int a, int b){
        // 辗转相除法
        int mod = 0;
        while (b != 0){
            mod = a % b;
            if (mod == 0) {
                return b;
            }
            a = b;
            b = mod;
        }
        return 1;
    }
}
